COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	% This program by D. E. Knuth is not copyrighted and can be used freely.
C00006 00003	@* Breaking paragraphs into lines.
C00067 00004	@* Breaking paragraphs into lines, continued.
C00095 ENDMK
C⊗;
% This program by D. E. Knuth is not copyrighted and can be used freely.
% Please don't make any changes to this file unless you are D. E. Knuth!
% Version 0 is presently being implemented.

% Here is TeX material that gets inserted after \input webhdr
% I will modify it later so that TEX.WEB works unmagnified, while
% TEX.CH gives the format used in the published book.
\def\pagewidth{29pc}\def\pageheight{44pc}\def\fullpageheight{47pc}
\magnify{1200}\setpage
\def\lheader{\hbox to0pt{\hss\:q\count0\hskip1pc}\:m\rhead\hfill\title\qquad
	\:ux\:a\topmark} % top line on left-hand pages
\def\rheader{\:ux\:a\topmark\:m\qquad\title\hfill\rhead
	\hbox to0pt{\hskip1pc\:q\count0\hss}} % top line on right-hand pages
\def\hang{\hangindent 3em\ \unskip\!}
\def\textindent#1{\hangindent 2.5em\noindent\hbox to 2.5em{\hss#1 }\!}
\def\at{@@} % use for an at sign
\chcode@@=13 \def@@{\penalty999\ } % ties words together
\def\TeX{T\hbox{\hskip-.1667em\lower.424ex\hbox{E}\hskip-.125em X}}
\font b=cmr9 \def\mc{\:b} % medium caps for names like PASCAL
\def\PASCAL{{\mc PASCAL}}
\def\ph{{\mc PASCAL-H}}
\font L=manfnt % font used for the METAFONT logo
\def\MF{{\:L META}\-{\:L FONT}}
\def\<#1>{$\langle#1\rangle$}
\def\kern{\penalty100000\hskip}

\def\(#1){} % this is used to make module names sort themselves better
\def\9#1{} % this is used for sort keys in the index via @@:sort key}{entry@@>
\def\6{\ifmmode{}\else{\hbox to -30pt{\hss}\par % break allowing 30pt stickout
	\hangindent\count7em\noindent\hskip\count7em\copy2}}

\font D=cmtt at 15truept % font used in the title line below (only)
\font E=cmr7 at 14truept % font used in the title line below (only)

\def\title{\TeX82}
\def\contentspagenumber{101}
\def\topofcontents{\topspace 0pt
	\vfill
	\ctrline{\:E The {\:D \TeX} processor}
	\vskip 15pt
	\ctrline{(preliminary version, in preparation)}
	\vfill}
\def\botofcontents{\vfill
	\ctrline{\ragged0\spaceskip0pt\xspaceskip0pt\baselineskip9pt
		\hbox par 5in{\:bThe preparation of this report
		was supported in part by the National Science
		Foundation under grants IST-8201926 and MCS-7723738;
		by Office of Naval Research grant N00014-81-K-0330;
		and by the System Development Foundation. `\TeX' is a
		trademark of the American Mathematical Society.}}}
\setcount0 \contentspagenumber
\topofcontents
\ctrline{(replace this page by the contents page printed later)}
\botofcontents
\mark{1}\eject
@* Breaking paragraphs into lines.
We come now to what is probably the most interesting algorithm of \TeX:
the mechanism for choosing the ``best possible'' breakpoints that yield
the individual lines of a paragraph. \TeX's line-breaking algorithm takes
a given horizontal list and converts it to a sequence of boxes that are
appended to the current vertical list. In the course of doing this, it
creates a special data structure containing three kinds of records that are
not used elsewhere in \TeX. Such nodes are created while a paragraph is
being processed, and they are destroyed afterwards; thus, the other parts
of \TeX\ do not need to know anything about how line-breaking is done.

The method used here is based on an approach devised by Michael F. Plass and
@↑Plass, Michael Frederick@>
@↑Knuth, Donald Ervin@>
the author in 1977, subsequently generalized and improved by the same two
people in 1980. A detailed discussion appears in {\sl SOFTWARE---Practice
\AM\ Experience \bf11} (1981), 1119--1184, where it is shown that the
line-breaking problem can be regarded as a special case of the problem of
computing the shortest path in an acyclic network. The cited paper includes
numerous examples and describes the history of line breaking as it has been
practiced by printers through the ages. The present implementation adds two
new ideas to the algorithm of 1980: memory space requirements are considerably
reduced by using smaller records for inactive nodes than for active ones,
and arithmetic overflow is avoided by using ``delta distances'' instead of
keeping track of the total distance from the beginning of the paragraph to the
current point.

@ The |line_break| procedure should be invoked only in horizontal mode; it
leaves that mode and places its output into the current vlist of the
enclosing vertical mode (or internal vertical mode).
There is one explicit parameter:  |final_widow_penalty| is the amount of
additional penalty to be inserted before the final line of the paragraph.

There are also a number of implicit parameters: The hlist to be broken
starts at |link(head)|, and it is nonempty. The value of |already| in the
enclosing semantic level tells where the paragraph should begin in the
sequence of line numbers, in case hanging indentation or \.{\\parshape}
are in use; |already| is zero unless this paragraph is being continued
after a displayed formula.  Other implicit parameters, such as the
|par_shape_ptr| and various penalties to use for hyphenation, etc., appear
in |eqtb|.

After |line_break| has acted, it will have updated the current vlist and the
value of |already|. Furthermore, the global variable |just_box| will
point to the final box created by |line_break|, so that the width of this
line can be ascertained when it is necessary to decide whether to use
|disp_skip| or |disp_a_skip| before a displayed formula.

@<Glob...@>=
@!just_box:pointer; {the |hlist_node| for the last line of the new paragraph}

@ Since |line_break| is a rather lengthy procedure---sort of a small world unto
itself---we must build it up little by little, somewhat more cautiously
than we have done with the simpler procedures of \TeX. Here is the
general outline.

@p procedure line_break(@!final_widow_penalty:integer); 
label done,done1,done2,done3,done4,done5,done6,done7,found,not_found;
var@?@<Local variables for line breaking@>@;
@t\4@>@<Declare the local procedure called |try_break|@>@;
@t\4@>@<Declare the local function called |reconstitute|@>@;
@t\4@>@<Declare the local function called |finite_shrink|@>@;
begin par_begin_line←mode_line; {this is for over/underfull box messages}
@<Get ready to start line breaking@>;
@<Find optimal breakpoints@>;
@<Break the paragraph at the chosen breakpoints, justify the resulting lines
to the correct widths, and append them to the current vertical list@>;
@<Clean up the memory by removing the break nodes@>;
par_begin_line←0;
end;

@ The first task is to move the list from |head| to |temp_head| and go
into the enclosing semantic level. We also append the \.{\\parfillskip}
glue to the end of the paragraph, removing a space (or other glue node) if
it was there, since spaces usually precede blank lines and instances of
`\.{\$\$}'. The |par_fill_skip| is preceded by an infinite penalty, so
it will never be considered as a potential breakpoint.

This code assumes that a |glue_node| and a |penalty_node| occupy the
same number of words in |mem|.

@<Get ready...@>=
link(temp_head)←link(head);
if is_char_node(tail) then tail_append(new_penalty(inf_penalty))
else if (type(tail)≠glue_node)∨(subtype(tail)≥a_leaders) then
	tail_append(new_penalty(inf_penalty))
else	begin type(tail)←penalty_node; delete_glue_ref(glue_ptr(tail));
	penalty(tail)←inf_penalty;
	end;
link(tail)←new_param_glue(par_fill_skip_code);
pop_nest;

@ When looking for optimal line breaks, \TeX\ creates a ``break node'' for
each break that is {\sl feasible}, in the sense that there is a way to end
a line at the given place without requiring any line to stretch more than
a given tolerance. A break node is characterized by three things: the position
of the break (which is a pointer to a |glue_node|, |math_node|, |penalty_node|,
or |disc_node|); the ordinal number of the line that will follow this
breakpoint; and the fitness classification of the line that has just
ended, i.e., |tight_fit|, |decent_fit|, |loose_fit|, or |very_loose_fit|.

@d tight_fit=0 {fitness classification for lines shrinking 0.5 to 1.0 of their
	shrinkability}
@d loose_fit=2 {fitness classification for lines stretching 0.5 to 1.0 of their
	stretchability}
@d very_loose_fit=3 {fitness classification for lines stretching more than
	their stretchability}
@d decent_fit=1 {fitness classification for all other lines}

@ The algorithm essentially determines the best possible way to achieve
each feasible combination of position, line, and fitness. Thus, it answers
questions like, ``What is the best way to break the opening part of the
paragraph so that the fourth line is a tight line ending at such-and-such
a place?'' However, the fact that all lines are to be the same length
after a certain point makes it possible to regard all sufficiently large
line numbers as equivalent, when the looseness parameter is zero, and this
makes it possible for the algorithm to save space and time.

An ``active node'' and a ``passive node'' are created in |mem| for each
feasible breakpoint that needs to be considered. Active nodes are three
words long and passive nodes are two words long. We need active nodes only
for breakpoints near the place in the paragraph that is currently being
examined, so they are recycled within a comparatively short time after
they are created.

@ An active node for a given breakpoint contains six fields:

\yskip\hang|link| points to the next node in the list of active nodes; the
last active node has |link=last_active|.

\yskip\hang|break_node| points to the passive node associated with this
breakpoint.

\yskip\hang|line_number| is the number of the line that follows this
breakpoint.

\yskip\hang|fitness| is the fitness classification of the line ending at this
breakpoint.

\yskip\hang|type| is either |hyphenated| or |unhyphenated|, de\-pending on
whether this breakpoint is a |disc_node|.

\yskip\hang|total_demerits| is the minimum possible sum of demerits over all
lines leading from the beginning of the paragraph to this breakpoint.

\yskip\noindent
The value of |link(active)| points to the first active node on a linked list
of all currently active nodes. This list is in order by |line_number|,
except that nodes with |line_number>easy_line| may be in any order relative
to each other.

@d active_node_size=3 {number of words in active nodes}
@d fitness==subtype {|tight_fit..very_loose_fit| on final line for this break}
@d break_node==rlink {pointer to the corresponding passive node}
@d line_number==llink {line that begins at this breakpoint}
@d total_demerits(#)==mem[#+2].int {the quantity that \TeX\ minimizes}
@d unhyphenated=0 {the |type| of a normal active break node}
@d hyphenated=1 {the |type| of an active node that breaks at a |disc_node|}
@d last_active==active {the active list ends where it begins}

@ @<Initialize the special list head...@>=
type(last_active)←hyphenated; line_number(last_active)←max_halfword;
subtype(last_active)←0; {the |subtype| is never examined by the algorithm}

@ The passive node for a given breakpoint contains only three fields:

\yskip\hang|link| points to the passive node created just before this one,
if any, otherwise it is |null|.

\yskip\hang|cur_break| points to the position of this breakpoint in the
horizontal list for the paragraph being broken.

\yskip\hang|prev_break| points to the passive node that should precede this
one in an optimal path to this breakpoint.

\yskip\noindent
There is a local variable called |passive| that points to the most
recently created passive node.

@d passive_node_size=2 {number of words in passive nodes}
@d cur_break==mark_ptr {in passive node, points to position of this breakpoint}
@d prev_break==info {points to passive node that should precede this one}

@<Local variables for line breaking@>=
@!passive:pointer; {most recent node on passive list}

@ The active list also contains ``delta'' nodes that help the algorithm
compute the badness of individual lines. Such nodes appear only between two
active nodes, and they have |type=delta|. If |p| and |r| are active nodes
and if |q| is a delta node between them, so that |link(p)=q| and |link(q)=r|,
then |q| tells the space difference between lines in the horizontal list that
start after breakpoint |p| and lines that start after breakpoint |r|. In
other words, if we know the length of the line that starts after |p| and
ends at our current position, then the corresponding length of the line that
starts after |r| is obtained by adding the amounts in node@@|q|. A delta node
contains six scaled numbers, since it must record the net change in glue
stretchability with respect to all orders of infinity. The natural width
difference appears in |mem[q+1].sc|; the stretch differences in units of
pt, fil, fill, and filll appear in |mem[q+2..q+5].sc|; and the shrink difference
appears in |mem[q+6].sc|. The |subtype| field of a delta node is not used.

@d delta_node_size=7 {number of words in a delta node}
@d delta_node=2 {|type| field in a delta node}

@ As the algorithm runs, it maintains a set of six delta-like registers
for the length of the line following the first active breakpoint to the
current position in the given hlist. When it makes a pass through the
active list, it also maintains a similar set of six registers for the
length following the active breakpoint of current interest. A third set
holds the length of an empty line (namely, the sum of \.{\\leftskip} and
\.{\\rightskip}); and a fourth set is used to create new delta nodes.

When we pass a delta node we want to do operations like `\!|for k←1 to 6 do
cur_active_width[k]←cur_active_width[k]+mem[q+k].sc|', and we want to
do this without the overhead of |for| loops. The |do_all_six| macro
makes such six-tuples convenient.

@d do_all_six(#)==#(1);#(2);#(3);#(4);#(5);#(6)

@<Glo...@>=
@!active_width:array[1..6] of scaled; {distance from first active node to@@|p|}
@!cur_active_width:array[1..6] of scaled; {distance from current active node}
@!background:array[1..6] of scaled; {length of an ``empty'' line}
@!break_width:array[1..6] of scaled; {length being computed after current break}

@ Let's state the principles of the delta nodes more precisely and concisely,
so that the following programs will be less obscure. For each legal
breakpoint@@$p$ in the paragraph, we define two quantities $\alpha(p)$ and
$\beta(p)$ such that the length of material in a line from breakpoint@@$p$
to breakpoint@@$q$ is $\gamma+\beta(q)-\alpha(p)$, for some fixed $\gamma$.
Intuitively, $\alpha(p)$ and $\beta(q)$ are the total length of material from
the beginning of the paragraph to a point ``after'' a break at $p$ and to a
point ``before'' a break at $q$; and $\gamma$ is the width of an empty line,
namely the length contributed by \.{\\leftskip} and \.{\\rightskip}.

Suppose, for example, that the paragraph consists entirely of alternating
boxes and glue skips; let the boxes have widths $x↓1\ldotsm x↓n$ and
let the skips have widths $y↓1\ldotsm y↓n$, so that the paragraph can be
represented by $x↓1y↓1\ldotsm x↓ny↓n$. Let $p↓i$ be the legal breakpoint
at $y↓i$; then $\alpha(p↓i)=x↓1+y↓1+\cdots+x↓i+y↓i$, and $\beta(p↓i)=
x↓1+y↓1+\cdots+x↓i$. To check this, note that the length of material from
$p↓2$ to $p↓5$, say, is $\gamma+x↓3+y↓3+x↓4+y↓4+x↓5=\gamma+\beta(p↓5)
-\alpha(p↓2)$.

The quantities $\alpha$, $\beta$, $\gamma$ involve glue stretchability and
shrinkability as well as a natural width. If we were to compute $\alpha(p)$
and $\beta(p)$ for each $p$, we would need multiple precision arithmetic, and
the multiprecise numbers would have to be kept in the active nodes.
\TeX\ avoids this problem by working entirely with relative differences
or ``deltas.'' Suppose, for example, that the active list contains
$a↓1\,\delta↓1\,a↓2\,\delta↓2\,a↓3$, where the $a$'s are active breakpoints
and the $\delta$'s are delta nodes. Then $\delta↓1=\alpha(a↓1)-\alpha(a↓2)$
and $\delta↓2=\alpha(a↓2)-\alpha(a↓3)$. If the line breaking algorithm is
currently positioned at some other breakpoint $p$, the |active_width| array
contains the value $\gamma+\beta(p)-\alpha(a↓1)$. If we are scanning through
the list of active nodes and considering a tentative line that runs from
$a↓2$ to@@$p$, say, the |cur_active_width| array will contain the value
$\gamma+\beta(p)-\alpha(a↓2)$. Thus, when we move from $a↓2$ to $a↓3$,
we want to add $\alpha(a↓2)-\alpha(a↓3)$ to |cur_active_width|; and this
is just $\delta↓2$, which appears in the active list between $a↓2$ and
$a↓3$. The |background| array contains $\gamma$. The |break_width| array
will be used to calculate values of new delta nodes when the active
list is being updated.

@ Glue nodes in a horizontal list that is being paragraphed are not supposed to
include ``infinite'' shrinkability; that is why the algorithm maintains
four registers for stretching but only one for shrinking. If the user tries to
introduce infinite shrinkability, the shrinkability will be reset to finite
and an error message will be issued. A boolean variable |no_shrink_error_yet|
prevents this error message from appearing more than once per paragraph.

@d check_shrinkage(#)==if shrink_order(#)≠normal then
	begin #←finite_shrink(#);
	end

@<Local variables for line...@>=
@!no_shrink_error_yet:boolean; {have we complained about infinite shrinkage?}

@ @<Get ready...@>=no_shrink_error_yet←false;

@ @<Declare the local function called |finite_shrink|@>=
function finite_shrink(@!p:pointer):pointer; {recovers from infinite shrinkage}
var q:pointer; {new glue specification}
begin if no_shrink_error_yet then
	begin no_shrink_error_yet←false;
	help5("The paragraph just ended includes some glue that has")@/
	("infinite shrinkability, e.g., `\hskip 0pt minus 1fil'.")@/
	("Such glue doesn't belong there---it allows a paragraph")@/
	("of any length to fit on one line. But it's safe to proceed,")@/
	("since the offensive shrinkability has been made finite.");
	print_nl("! Infinite glue shrinkage found in a paragraph"); error;
@.Infinite glue shrinkage...@>
	end;
q←new_spec(p); shrink_order(q)←normal;
delete_glue_ref(p); finite_shrink←q;
end;

@ @<Get ready...@>=
check_shrinkage(left_skip); check_shrinkage(right_skip);@/
q←left_skip; r←right_skip; background[1]←width(q)+width(r);@/
background[2]←0; background[3]←0; background[4]←0; background[5]←0;@/
background[2+stretch_order(q)]←stretch(q);@/
background[2+stretch_order(r)]←@|background[2+stretch_order(r)]+stretch(r);@/
background[6]←shrink(q)+shrink(r);

@ A pointer variable |p| runs through the given horizontal list as we look
for breakpoints.

Another variable called |threshold| is used to determine the feasibility
of individual lines: breakpoints are feasible if there is a way to reach
them without creating lines whose badness exceeds |threshold|.  (The
badness is compared to |threshold| before penalties are added, so that
penalty values do not affect the feasibility of breakpoints, except that
no break is allowed when the penalty is 10000 or more.) If |threshold|
is 10000 or more, all legal breaks are considered feasible, since the
|badness| function specified above never returns a value greater than
10000.

Two passes might be made through the paragraph in an attempt to find at
least one set of feasible breakpoints. On the first pass, we have
|threshold=pretolerance| and |second_pass=false|. If this pass fails to find a
feasible solution, |threshold| is set to |tolerance|, |second_pass| is set
|true|, and an attempt is made to hyphenate as many words as possible.

@<Local variables for line breaking@>=
@!p:pointer; {the current candidate for breaking in the hlist}
@!second_pass:boolean; {is this our second attempt to break this paragraph?}
@!threshold:integer; {maximum badness on feasible lines}

@ The heart of the line-breaking procedure is `|try_break|', a subroutine
that tests if the current breakpoint |p| is feasible, by running through
the active list to see what lines of text can be made from active nodes to |p|.
If feasible breaks are possible, new break nodes are created.
If |p| is too far from an active node, that node is deactivated.

The parameter |pi| to |try_break| is the penalty associated
with a break at |p|; we have |pi=eject_penalty| if the break is forced,
and |pi=inf_penalty| if the break is illegal.

The other parameter, |break_type|, is set to |hyphenated| or |unhyphenated|,
de\-pending on whether or not the current break is at a |disc_node|. The
end of a para\-graph is also regarded as `|hyphenated|'; this case is
distinguishable by the condition |p=null|.

@d copy_to_cur_active(#)==cur_active_width[#]←active_width[#]
@d deactivate=60 {go here when node |r| should be deactivated}

@<Declare the local procedure called |try_break|@>=
procedure try_break(@!pi:integer;@!break_type:small_number);
label exit,done,continue,deactivate;
var r:pointer; {runs through the active list}
@!prev_r:pointer; {stays a step behind |r|}
@!old_l:halfword; {maximum line number in current equivalence class of lines}
@!no_break_yet:boolean; {have we found a feasible break at |p|?}
@<Other local variables for |try_break|@>@;
begin @<Make sure that |pi| is in the proper range@>;
no_break_yet←true; prev_r←active; old_l←0;
do_all_six(copy_to_cur_active);
loop@+	begin continue: r←link(prev_r);
	@<If node |r| is of type |delta_node|, update |cur_active_width|,
		set |prev_r| and |prev_prev_r|, then |goto continue|@>;
	@<If a line number class has ended, create new active nodes for
		the best feasible breaks in that class; then |return|
		if |r=last_active|, otherwise compute the new |line_width|@>;
	@<Consider the demerits for a line from |r| to |p|;
		deactivate node |r| if it should no longer be active;
		then |goto continue| if a line from |r| to |p| is infeasible,
		otherwise record a new feasible break@>;
	end;
exit:end;

@ @<Other local variables for |try_break|@>=
@!prev_prev_r:pointer; {a step behind |prev_r|, if |type(prev_r)=delta_node|}
@!s:pointer; {runs through nodes ahead of |p|}
@!q:pointer; {points to a new node being created}
@!v:pointer; {points to a glue specification}
@!t:quarterword; {replacement count, if |p| is a discretionary node}
@!f:internal_font_number; {used in character width calculation}
@!l:halfword; {line number of current active node}
@!node_r_stays_active:boolean; {should node |r| remain in the active list?}
@!line_width:scaled; {the current line will be justified to this width}
@!fit_class:tight_fit..very_loose_fit; {possible fitness class of test line}
@!b:halfword; {badness of test line}
@!d:integer; {demerits of test line}

@ @<Make sure that |pi| is in the proper range@>=
if abs(pi)≥inf_penalty then
	if pi>0 then return {this breakpoint is inhibited by infinite penalty}
	else pi←eject_penalty {this breakpoint will be forced}

@ The following code uses the fact that |type(last_active)≠delta_node|.

@d update_width(#)==@|
	cur_active_width[#]←cur_active_width[#]+mem[r+#].sc

@<If node |r|...@>=
if type(r)=delta_node then
	begin do_all_six(update_width);
	prev_prev_r←prev_r; prev_r←r; goto continue;
	end

@ As we consider various ways to end a line at |p|, in a given line number
class, we keep track of the best known total demerits, in an array containing
one entry for each of the fitness classifications. For example,
|minimal_demerits[tight_fit]| contains the fewest total demerits of feasible
line breaks ending at |p| with a |tight_fit| line; |best_place[tight_fit]|
points to the passive node for the break before@@|p| that achieves such
an optimum; and |best_pl_line[tight_fit]| is the |line_number| field in the
active node corresponding to |best_place[tight_fit]|. When no feasible break
sequence is known, the |minimal_demerits| entries will be equal to
|awful_bad|, which is $2↑{30}-1$. Another variable, |minimum_demerits|,
keeps track of the smallest value in the |minimal_demerits| array.

@d awful_bad==@'7777777777 {more than a billion demerits}

@<Global...@>=
@!minimal_demerits:array[tight_fit..very_loose_fit] of scaled; {best total
	demerits known for current line class and position, given the fitness}
@!minimum_demerits:scaled; {best total demerits known for current line class
	and position}
@!best_place:array[tight_fit..very_loose_fit] of pointer; {how to achieve
	|minimal_demerits|}
@!best_pl_line:array[tight_fit..very_loose_fit] of halfword; {corresponding
	line number}

@ @<Get ready...@>=
minimum_demerits←awful_bad;
minimal_demerits[tight_fit]←awful_bad;
minimal_demerits[decent_fit]←awful_bad;
minimal_demerits[loose_fit]←awful_bad;
minimal_demerits[very_loose_fit]←awful_bad;

@ The first part of the following code is part of \TeX's inner loop, so
we don't want to waste any time. The current active node, namely node |r|,
contains the line number that will be considered next. At the end of the
list we have arranged the data structure so that |r=last_active| and
|line_number(last_active)>old_l|.
@↑inner loop@>

@<If a line number class...@>=
begin l←line_number(r);
if l>old_l then
	begin {now we are no longer in the inner loop}
	if (minimum_demerits<awful_bad)∧@|
			((old_l≠easy_line)∨(r=last_active)) then
		@<Create new active nodes for the best feasible breaks
			just found@>;
	if r=last_active then return;
	@<Compute the new line width@>;
	end;
end

@ It is not necessary to create new active nodes having |minimal_demerits
>minimum_demerits+abs(adj_demerits)|, since such active nodes will never
be chosen in the final paragraph breaks. This observation allows us to
omit a substantial number of feasible breakpoints from further consideration.

@<Create new active nodes...@>=
begin if no_break_yet then @<Compute the values of |break_width|@>;
@<Insert a delta node to prepare for breaks at |p|@>;
minimum_demerits←minimum_demerits+abs(adj_demerits);
for fit_class←tight_fit to very_loose_fit do
	begin if minimal_demerits[fit_class]≤minimum_demerits then
		@<Insert a new active node
			from |best_place[fit_class]| to |p|@>;
	minimal_demerits[fit_class]←awful_bad;
	end;
minimum_demerits←awful_bad;
@<Insert a delta node to prepare for the next active node@>;
end

@ When we insert a new active node for a break at |p|, suppose this new node
is to be placed just before active node |a|; then we essentially want to
insert `$\delta\,p\,\delta↑\prime$' before $a$, where $\delta=\alpha(a)-
\alpha(p)$ and $\delta↑\prime=\alpha(p)-\alpha(a)$ in the notation explained
above. The |cur_active_width| array now hold $\gamma+\beta(p)-\alpha(a)$;
so $\delta$ can be obtained by subtracting |cur_active_width| from the
quantity $\gamma+\beta(p)-\alpha(p)$. The latter quantity can be regarded
as the length of a line ``from $p$ to $p$''; we call it the |break_width|
at $p$.

The |break_width| is usually negative, since it consists of the background
(which is normally zero) minus the width of nodes following@@|p| that are
eliminated after a break. If, for example, node |p| is a glue node, the
width of this glue is subtracted from the background; and we also look
ahead to eliminate all subsequent glue and penalty and kern and math
nodes, subtracting their widths as well.

@d set_break_width_to_background(#)==break_width[#]←background[#]

@<Compute the values of |break...@>=
begin no_break_yet←false; do_all_six(set_break_width_to_background);
if (break_type=unhyphenated)∨(p=null) then
	begin s←p;
	while s≠null do
		begin if is_char_node(s) then goto done;
		case type(s) of
		glue_node:@<Subtract glue from |break_width|@>;
		penalty_node: do_nothing;
		math_node,kern_node: break_width[1]←break_width[1]-width(s);
		othercases goto done
		endcases;@/
		s←link(s);
		end;
	end
else @<Compute the discretionary |break_width| values@>;
done: end

@ @<Subtract glue from |break...@>=
begin v←glue_ptr(s); break_width[1]←break_width[1]-width(v);
break_width[2+glue_order(v)]←break_width[2+glue_order(v)]-stretch(v);
break_width[6]←break_width[6]-shrink(v);
end

@ When |p| is a discretionary break, the length of a line ``from |p| to
|p|'' has to be defined properly so that the other calculations work out.
Suppose that the pre-break text at |p| has length $l↓0$, the post-break
text has length $l↓1$, and the replacement text has length $l$. Suppose
also that |q| is the node following the replacement text. Then length of a
line from |p| to |q| will be computed as $\gamma+\beta(q)-\alpha(p)$,
where $\beta(q)=\beta(p)-l↓0+l$.  The actual length will be the background
plus $l↓1$, so the length from $p$ to $p$ should be $\gamma+l↓0+l↓1-l$.

The value of $l↓0$ need not be computed, since it appears in the variable@@|w|
(which is global to |try_break| and local to |line_break|).

@<Compute the discretionary |break...@>=
begin t←replace_count(p); s←p;
while t>0 do
	begin decr(t); s←link(s);
	@<Subtract the width of node |s| from |break_width|@>;
	end;
s←post_break(p);
while s≠null do
	begin @<Add the width of node |s| to |break_width|@>;
	s←link(s);
	end;
break_width[1]←break_width[1]+w;
end

@ Replacement texts and discretionary texts are supposed to contain
only character nodes, kern nodes, and ligature nodes.

@<Subtract the width of node |s|...@>=
if is_char_node(s) then
	begin f←font(s);
	break_width[1]←break_width[1]-char_width(f)(char_info(f)(character(s)));
	end
else	case type(s) of
	ligature_node: begin f←font(lig_char(s));@/
		break_width[1]←@|break_width[1]-
			char_width(f)(char_info(f)(character(lig_char(s))));
		end;
	kern_node: break_width[1]←break_width[1]-width(s);
	othercases confusion("disc1")
@:confusion disc1}{\quad disc1@>
	endcases

@ @<Add the width of node |s| to |b...@>=
if is_char_node(s) then
	begin f←font(s);
	break_width[1]←@|break_width[1]+char_width(f)(char_info(f)(character(s)));
	end
else	case type(s) of
	ligature_node: begin f←font(lig_char(s));
		break_width[1]←break_width[1]+
			char_width(f)(char_info(f)(character(lig_char(s))));
		end;
	kern_node: break_width[1]←break_width[1]+width(s);
	othercases confusion("disc2")
@:confusion disc2}{\quad disc2@>
	endcases

@ We use the fact that |type(active)≠delta_node|.

@d convert_to_break_width(#)==@|
	mem[prev_r+#].sc←@|@t\hskip10pt@>mem[prev_r+#].sc
	-cur_active_width[#]+break_width[#]
@d store_break_width(#)==active_width[#]←break_width[#]
@d new_delta_to_break_width(#)==@|
	mem[q+#].sc←break_width[#]-cur_active_width[#]

@<Insert a delta node to prepare for breaks at |p|@>=
if type(prev_r)=delta_node then {modify an existing delta node}
	begin do_all_six(convert_to_break_width);
	end
else if prev_r=active then {no delta node needed at the beginning}
	begin do_all_six(store_break_width);
	end
else	begin q←get_node(delta_node_size); link(q)←r; type(q)←delta_node;
	subtype(q)←0; {the |subtype| is not used}
	do_all_six(new_delta_to_break_width);
	link(prev_r)←q; prev_prev_r←prev_r; prev_r←q;
	end

@ When the following code is performed, we will have just inserted at
least one active node before |r|, so |type(prev_r)≠delta_node|.

@d new_delta_from_break_width(#)==@|mem[q+#].sc←
		cur_active_width[#]-break_width[#]

@<Insert a delta node to prepare for the next active node@>=
if r≠last_active then
	begin q←get_node(delta_node_size); link(q)←r; type(q)←delta_node;
	subtype(q)←0; {the |subtype| is not used}
	do_all_six(new_delta_from_break_width);
	link(prev_r)←q; prev_prev_r←prev_r; prev_r←q;
	end

@ When we create an active node, we also create the corresponding
passive node.

@<Insert a new active node from |best_place[fit_class]| to |p|@>=
begin q←get_node(passive_node_size);
link(q)←passive; passive←q; cur_break(q)←p;
prev_break(q)←best_place[fit_class];@/
q←get_node(active_node_size); break_node(q)←passive;
line_number(q)←best_pl_line[fit_class]+1;
fitness(q)←fit_class; type(q)←break_type;
total_demerits(q)←minimal_demerits[fit_class];
link(q)←r; link(prev_r)←q; prev_r←q;
end

@ The length of lines depends on whether the user has specified
\.{\\parshape} or \.{\\hangindent}. If |par_shape_ptr| is not null, it
points to a $(2n+1)$-word record in |mem|, where the |info| in the first
word contains the value of |n|, and the other $2n$ words contain the left
margins and line lengths for the first |n| lines of the paragraph; the
specifications for line |n| apply to all subsequent lines. If
|par_shape_ptr=null|, the shape of the paragraph depends on the value of
|n=hang_after|; if |n≥0|, hanging indentation takes place on lines |n+1|,
|n+2|, $\ldotss$, otherwise it takes place on lines 1, $\ldotss$, $\leftv
n\rightv$. When hanging indentation is active, the left margin is
|hanging_indent|, if |hanging_indent≥0|, else it is 0; the line length is
$|hsize|-\leftv|hanging_indent|\rightv$. The normal setting is
|par_shape_ptr=null|, |hang_after=0|, and |hanging_indent=0|.  @↑length of
lines@> @↑hanging indentation@> Note that if |hanging_indent=0|, the value
of |hang_after| is irrelevant.

@<Local variables for line...@>=
@!easy_line:halfword; {line numbers |>easy_line| are equivalent in break nodes}
@!last_special_line:halfword; {line numbers |>last_special_line| all have
	the same width}
@!first_width:scaled; {the width of all lines |≤last_special_line|, if
	no \.{\\parshape} has been specified}
@!second_width:scaled; {the width of all lines |>last_special_line|}
@!first_indent:scaled; {left margin to go with |first_width|}
@!second_indent:scaled; {left margin to go with |second_width|}

@ We compute the values of |easy_line| and the other local variables relating
to line length when the |line_break| procedure is initializing itself.

@<Get ready...@>=
if par_shape_ptr=null then
	if hanging_indent=0 then
		begin last_special_line←0; first_width←hsize;
		second_width←first_width;
		end
	else @<Set line length parameters in preparation for hanging indentation@>
else	begin last_special_line←info(par_shape_ptr)-1;
	second_width←mem[par_shape_ptr+2*(last_special_line+1)].sc;
	second_indent←mem[par_shape_ptr+2*last_special_line+1].sc;
	end;
if looseness=0 then easy_line←last_special_line
else easy_line←max_halfword

@ @<Set line length parameters in preparation for hanging indentation@>=
begin last_special_line←abs(hang_after);
if hang_after<0 then
	begin first_width←hsize-abs(hanging_indent);
	if hanging_indent≥0 then first_indent←hanging_indent
	else first_indent←0;
	second_width←hsize; second_indent←0;
	end
else	begin first_width←hsize; first_indent←0;
	second_width←hsize-abs(hanging_indent);
	if hanging_indent≥0 then second_indent←hanging_indent
	else second_indent←0;
	end;
end

@ When we come to the following code, we have just encountered the first
active node@@|r| whose |line_number| field contains |l|. Thus we want to
compute the length of the $l\,$th line of the current paragraph. Furthermore
we want to set |old_l| to the last number in the class of line numbers
equivalent to@@|l|.

@<Compute the new line width@>=
if l>easy_line then
	begin line_width←second_width; old_l←max_halfword-1;
	end
else	begin old_l←l;
	if l>last_special_line then line_width←second_width
	else if par_shape_ptr=null then line_width←first_width
	else line_width←mem[par_shape_ptr+2*l@,].sc;
	end

@ The remaining part of |try_break| deals with the calculation of
demerits for a break from |r| to |p|.

The first thing to do is calculate the badness, |b|. This value will always
be between zero and |inf_bad+1|; the latter value occurs only in the
case of lines from |r| to |p| that cannot shrink enough to fit the necessary
width. In such cases, node |r| will be deactivated.
We also deactivate node@@|r| when a break at@@|p| is forced, since future
breaks must go through a forced break.

@<Consider the demerits for a line from |r| to |p|...@>=
begin if cur_active_width[1]<line_width then
	@<Set the value of |b| to the badness for stretching the line,
		and compute the corresponding |fit_class|@>
else @<Set the value of |b| to the badness for shrinking the line,
		and compute the corresponding |fit_class|@>;
if (b>inf_bad)∨(pi=eject_penalty) then
	@<Prepare to deactivate node@@|r|, and |goto deactivate| unless
		there is a reason to consider lines of text from |r| to |p|@>
else	begin prev_r←r;
	if b>threshold then goto continue;
	node_r_stays_active←true;
	end;
@<Record a new feasible break@>;
if node_r_stays_active then goto continue; {|prev_r| has been set to |r|}
deactivate: @<Deactivate node |r|@>;
end

@ When a line must stretch, the available stretchability appears in the
subarray |cur_active_width[2..5]|, in units of points, fil, fill, and filll.

@<Set the value of |b| to the badness for stretching...@>=
if (cur_active_width[3]≠0)∨(cur_active_width[4]≠0)∨@|
	(cur_active_width[5]≠0) then
	begin b←0; fit_class←decent_fit; {infinite stretch}
	end
else	begin b←badness(line_width-cur_active_width[1],cur_active_width[2]);
	if b>12 then
		if b>99 then fit_class←very_loose_fit
		else fit_class←loose_fit
	else fit_class←decent_fit;
	end

@ Shrinkability is never infinite in a paragraph;
we can shrink the line from |r| to |p| by at most |cur_active_width[6]|.

@<Set the value of |b| to the badness for shrinking...@>=
begin if cur_active_width[1]-line_width>cur_active_width[6] then
	b←inf_bad+1
else b←badness(cur_active_width[1]-line_width,cur_active_width[6]);
if b>12 then fit_class←tight_fit@+else fit_class←decent_fit;
end

@ During the second pass, we dare not lose all active nodes, lest we lose
touch with the line breaks already found. The code shown here makes sure
that such a catastrophe does not happen, by permitting overfull boxes as
a last resort. This particular part of \TeX\ was a source of several subtle
bugs before the correct program logic was finally discovered; readers
who seek to ``improve'' \TeX\ should therefore think thrice before daring
to make any changes here.
@↑overfull boxes@>

@<Prepare to deactivate node@@|r|, and |goto deactivate| unless...@>=
begin if second_pass ∧ (minimum_demerits=awful_bad) ∧@|
	 (link(r)=last_active) ∧
	(prev_r=active) then b←0 {set badness zero, this break is forced}
else if b>threshold then goto deactivate;
node_r_stays_active←false;
end

@ When we get to this part of the code, the line from |r| to |p| is
feasible, its badness is@@|b|, and its fitness classification is |fit_class|.
We don't want to make an active node for this break yet, but we will
compute the total demerits and record them in the |minimal_demerits| array,
if such a break is the current champion among all ways to get to |p|
in a given line-number class and fitness class.

@<Record a new feasible break@>=
@<Compute the fewest total demerits, |d|, from the beginning to |p| via@@|r|@>;
if d≤minimal_demerits[fit_class] then
	begin minimal_demerits[fit_class]←d;
	best_place[fit_class]←break_node(r); best_pl_line[fit_class]←l;
	if d<minimum_demerits then minimum_demerits←d;
	end

@ @<Compute the fewest total demerits...@>=
if pi≥0 then
	begin d←(line_penalty+b+pi); d←d*d;
	end
else	begin d←line_penalty+b; d←d*d;
	if pi>eject_penalty then d←d-pi*pi;
	end;
d←d+total_demerits(r);
if (break_type=hyphenated)∧(type(r)=hyphenated) then
	if p≠null then d←d+double_hyphen_demerits
	else d←d+final_hyphen_demerits;
if abs(fit_class-fitness(r))>1 then d←d+adj_demerits

@ When an active node disappears, we must delete an adjacent delta node if the
active node was at the beginning or the end of the active list, or if it
was surrounded by delta nodes. We also must preserve the property that
|cur_active_width| represents the length of material from |link(prev_r)|
to@@|p|.

@d combine_two_deltas(#)==@|mem[prev_r+#].sc←mem[prev_r+#].sc+mem[r+#].sc
@d downdate_width(#)==@|cur_active_width[#]←cur_active_width[#]-
	mem[prev_r+#].sc

@<Deactivate node |r|@>=
link(prev_r)←link(r); free_node(r,active_node_size);
if prev_r=active then @<Update the active widths, since the first active
	node has been deleted@>
else if type(prev_r)=delta_node then
	begin r←link(prev_r);
	if r=last_active then
		begin do_all_six(downdate_width);
		link(prev_prev_r)←last_active;
		free_node(prev_r,delta_node_size); prev_r←prev_prev_r;
		end
	else if type(r)=delta_node then
		begin do_all_six(update_width);
		do_all_six(combine_two_deltas);
		link(prev_r)←link(r); free_node(r,delta_node_size);
		end;
	end

@ The following code uses the fact that |type(last_active)≠delta_node|. If the
active list has just become empty, we do not need to update the
|active_width| array, since it will be initialized when an active
node is next inserted.

@d update_active(#)==active_width[#]←active_width[#]+mem[r+#].sc

@<Update the active widths,...@>=
begin r←link(active);
if type(r)=delta_node then
	begin do_all_six(update_active);
	do_all_six(copy_to_cur_active);
	link(active)←link(r); free_node(r,delta_node_size);
	end;
end
@* Breaking paragraphs into lines, continued.
So far we have gotten a little way into the |line_break| routine, having
covered its important |try_break| subroutine. Now let's consider the
rest of the process.

The main loop of |line_break| traverses the hlist of the given paragraph,
starting at |link(temp_head)|, and calls |try_break| at each legal
breakpoint. A variable called |auto_breaking| is set to true except
within math formulas, since glue nodes are not legal breakpoints when
they appear in formulas.

The current node of interest in the hlist is pointed to by |p|. Another
local variable, |prev_p|, is usually one step behind |p|, but the real
meaning of |prev_p| is this: If |type(p)=glue_node| then |p| is a legal
breakpoint if and only if |auto_breaking| is true and |prev_p| does not
point to a glue node, penalty node, kern node, or math node.

The following declarations provide for a few other local variables that are
used in special calculations.

@<Local variables for line breaking@>=
@!auto_breaking:boolean; {is node |p| outside a formula?}
@!prev_p:pointer; {helps to determine when glue nodes are breakpoints}
@!q,@!r,@!s:pointer; {miscellaneous nodes of temporary interest}
@!t:quarterword; {used for replacement counts in discretionary nodes}
@!f:internal_font_number; {used when calculating character widths}
@!w:scaled; {the length of discretionary material preceding a break}
@!pen:integer; {use when calculating penalties between lines}

@ The `\!|loop|\unskip' in the following code is performed at most
twice per call of |line_break|, since it is actually a pass over the
entire paragraph.

@<Find optimal breakpoints@>=
threshold←pretolerance; second_pass←false;
loop@+	begin @<Create an active breakpoint representing the beginning of
		the paragraph@>;
	p←link(temp_head); auto_breaking←true;@/
	prev_p←p; {glue at beginning is not a legal breakpoint}
	while (p≠null)∧(link(active)≠last_active) do
		@<Call |try_break| if |p| is a legal breakpoint;
		on the second pass, also try to hyphenate the next
		word, if |p| is a glue node;
		then advance |p| to the next node of the paragraph
		that could possibly be a legal breakpoint@>;
	if p=null then
		@<Try the final line break at the end of the paragraph,
		and |goto done| if the desired breakpoints have been found@>;
	@<Clean up the memory by removing the break nodes@>;
	threshold←tolerance; second_pass←true; {if at first you don't
		succeed, $\ldotss$}
	end;
done:

@ The active node that represents the starting point does not need a
corresponding passive node. 

@d store_background(#)==active_width[#]←background[#]

@<Create an active breakpoint representing the beginning of the paragraph@>=
q←get_node(active_node_size);
type(q)←unhyphenated; fitness(q)←decent_fit;
link(q)←last_active; break_node(q)←null;
line_number(q)←already+1; total_demerits(q)←0; link(active)←q;
do_all_six(store_background)

@ @<Clean...@>=
q←link(active);
while q≠last_active do
	begin p←link(q);
	if type(q)=delta_node then free_node(q,delta_node_size)
	else free_node(q,active_node_size);
	q←p;
	end;
q←passive;
while q≠null do
	begin p←link(q);
	free_node(q,passive_node_size);
	q←p;
	end

@ Here is the main switch in the |line_break| routine, where legal breaks
are determined. As we move through the hlist, we need to keep the |active_width|
array up to date, so that the badness of individual lines is readily calculated
by |try_break|. It is convenient to use the short name |act_width| for
the component of active width that represents real width as opposed to glue.

@d act_width==active_width[1] {length from first active node to current node}
@d kern_break==begin@;
	if not is_char_node(link(p)) ∧ auto_breaking then
		if type(link(p))=glue_node then try_break(0,unhyphenated);
	act_width←act_width+width(p);
	end

@<Call |try_break| if |p| is a legal breakpoint...@>=
begin while is_char_node(p) do @<Advance \(p_)|p| to the node following the
	present character@>;
case type(p) of
hlist_node,vlist_node,rule_node: act_width←act_width+width(p);
whatsit_node: @<Advance \(pa)past a whatsit node in the |line_break| loop@>;
glue_node: begin @<If node |p| is a legal breakpoint, call |try_break|@>;
	@<Update the active widths by including the glue in |glue_ptr(p)|@>;
	if second_pass ∧ auto_breaking then
		@<Try to hyphenate the following word@>;
	end;
kern_node: kern_break;
ligature_node: begin f←font(lig_char(p));
	act_width←act_width+char_width(f)(char_info(f)(character(lig_char(p))));
	end;
disc_node: @<Try to break after a discretionary fragment@>;
math_node: begin auto_breaking←(subtype(p)=after); kern_break;
	end;
penalty_node: try_break(penalty(p),unhyphenated);
mark_node,ins_node,adjust_node: do_nothing;
othercases confusion("paragraph")
@:confusion paragraph}{\quad paragraph@>
endcases;@/
prev_p←p; p←link(p);
end

@ The code that passes over the characters of words in a paragraph is
part of \TeX's inner loop, so it has been streamlined for speed. We use
the fact that `\.{\\parfillskip}' glue appears at the end of each paragraph;
it is therefore unnecessary to check if |link(p)=null| when |p| is a
character node.

@<Advance \(p_)|p| to the node following the present character@>=
begin f←font(p);
act_width←act_width+char_width(f)(char_info(f)(character(p)));
p←link(p);
end

@ When node |p| is a glue node, we look at |prev_p| to see whether or not
a breakpoint is legal at |p|, as explained above.

@<If node |p| is a legal breakpoint, call...@>=
if auto_breaking then
	begin if is_char_node(prev_p) then try_break(0,unhyphenated)
	else if precedes_break(prev_p) then try_break(0,unhyphenated);
	end

@ @<Update the active widths by including the glue in |glue_ptr(p)|@>=
begin check_shrinkage(glue_ptr(p)); q←glue_ptr(p);
act_width←act_width+width(q);@|
active_width[2+stretch_order(q)]←@|
	active_width[2+stretch_order(q)]+stretch(q);@/
active_width[6]←active_width[6]+shrink(q);
end

@ The following code knows that discretionary texts contain
only character nodes, kern nodes, and ligature nodes.

@<Try to break after a discretionary fragment@>=
begin s←pre_break(p);
if s=null then try_break(ex_hyphen_penalty,hyphenated)
else	begin w←0;
	repeat @<Add the width of node |s| to |w|@>;
	s←link(s);
	until s=null;
	act_width←act_width+w;
	try_break(hyphen_penalty,hyphenated);
	act_width←act_width-w;
	end;
end

@ @<Add the width of node |s| to |w|@>=
if is_char_node(s) then
	begin f←font(s);
	w←w+char_width(f)(char_info(f)(character(s)));
	end
else	case type(s) of
	ligature_node: begin f←font(lig_char(s));
		w←w+char_width(f)(char_info(f)(character(lig_char(s))));
		end;
	kern_node: w←w+width(s);
	othercases confusion("disc3")
@:confusion disc3}{\quad disc3@>
	endcases

@ The forced line break at the paragraph's end will reduce the list of
breakpoints so that all active nodes represent breaks at |p=null|.
On the first pass, we insist on finding an active node that has the
correct ``looseness.'' On the second pass, there will be at least one active
node, and we will match the desired looseness as well as we can.

The local variable |best_bet| will be set to the active node for the best
way to break the paragraph, and a few other local variables are used to
help determine what is best.

@<Local variables for line breaking@>=
@!best_bet:pointer; {use this passive node and its predecessors}
@!fewest_demerits:integer; {the demerits associated with |best_bet|}
@!best_line:halfword; {line number following the last line of the new paragraph}
@!actual_looseness:integer; {the difference between |line_number(best_bet)|
	and the optimum |best_line|}
@!line_diff:integer; {the difference between the current line number and
	the optimum |best_line|}

@ @<Try the final line break at the end of the paragraph...@>=
begin try_break(eject_penalty,hyphenated);
if link(active)≠last_active then
	begin @<Find an active node with fewest demerits@>;
	if looseness=0 then goto done;
	@<Find the best active node for the desired looseness@>;
	if (actual_looseness=looseness)∨ second_pass then goto done;
	end;
end

@ @<Find an active node...@>=
r←link(active); fewest_demerits←awful_bad;
repeat if type(r)≠delta_node then if total_demerits(r)<fewest_demerits then
	begin fewest_demerits←total_demerits(r); best_bet←r;
	end;
r←link(r);
until r=last_active;
best_line←line_number(best_bet)

@ The adjustment for a desired looseness is a slightly more complicated
version of the loop just considered. Note that if a paragraph is broken
into segments by displayed equations, each segment will be subject to the
looseness calculation, independently of the other segments.

@<Find the best active node...@>=
begin r←link(active); actual_looseness←0;
repeat if type(r)≠delta_node then
	begin line_diff←line_number(p)-best_line;
	if ((line_diff<actual_looseness)∧(looseness≤line_diff))∨@|
	((line_diff>actual_looseness)∧(looseness≥line_diff)) then
		begin best_bet←p; actual_looseness←line_diff;
		fewest_demerits←total_demerits(r);
		end
	else if (line_diff=actual_looseness)∧@|
		(total_demerits(r)<fewest_demerits) then
		begin best_bet←p; fewest_demerits←total_demerits(r);
		end;
	end;
r←link(r);
until r=last_active;
best_line←line_number(best_bet);
end

@ Now the best sequence of breakpoints has been found, and the total number
of lines will be |best_line-already-1|. The last break is specified by
|break_node(best_bet)|, and this passive node points to the other breakpoints
via the |prev_break| links. The finishing-up phase starts by linking the
relevant passive nodes in forward order, changing |prev_break| to
|next_break|. (The |next_break| fields actually reside in the same memory
space as the |prev_break| fields did, but we give them a new name because
of their new significance.) Then the lines are justified, one by one.

@d next_break==prev_break {new name for |prev_break| after links are reversed}

@<Local variables for line breaking@>=
@!cur_line: halfword; {the current line number being justified}

@ @<Break the paragraph at the chosen breakpoints...@>=
@<Reverse the links of the relevant passive nodes, setting |p| to the
	first breakpoint@>;
cur_line←already+1;
repeat @<Justify the line ending at breakpoint |p|, and append it to the
	current vertical list, together with associated penalties and other
	insertions@>;
incr(cur_line); p←next_break(p);
@<Prune unwanted nodes at the beginning of the next line@>;
until p=null;
if (cur_line≠best_line)∨(link(temp_head)≠null) then
	confusion("line breaking");
@:confusion line breaking}{\quad line breaking@>
already←best_line-1

@ The job of reversing links in a list is conveniently regarded as the job
of taking items off one stack and putting them on another. In this case we
take them off a stack pointed to by |q| and having |prev_break| fields;
we put them on a stack pointed to by |p| and having |next_break| fields.
Node |r| is the passive node being moved from stack to stack.

@<Reverse the links of the relevant passive nodes...@>=
q←break_node(best_bet); p←null;
repeat r←q; q←prev_break(q); next_break(r)←p; p←r;
until q=null

@ Glue and penalty and kern and math nodes are deleted at the beginning of
a line, except in the unusual case that the node to be deleted is actually
one of the chosen breakpoints. The pruning done here is designed to match
the lookahead computation in |try_break|, where the |break_width| values
are computed for non-discretionary breakpoints.

@<Prune unwanted nodes at the beginning of the next line@>=
r←temp_head;
loop@+	begin q←link(r);
	if q=cur_break(p) then goto done1; {|cur_break(p)| is the next breakpoint}
	{now |q| cannot be |null|}
	if is_char_node(q) then goto done1;
	if precedes_break(q) then goto done1;
	{now |type(q)=glue_node|, |kern_node|, |math_node| or |penalty_node|}
	r←q;
	end;
done1: if r≠temp_head then
	begin link(r)←null; flush_node_list(link(temp_head));
	link(temp_head)←q;
	end

@ The current line to be justified appears in a horizontal list starting
at |link(temp_head)| and ending at |cur_break(p)|. If |cur_break(p)| is
a glue node, we reset the glue to equal the |right_skip| glue; otherwise
we append the |right_skip| glue at the right. If |cur_break(p)| is a
discretionary node, we modify the list so that the discretionary break
is compulsory, and we set |disc_break| to |true|. We also append
the |left_skip| glue at the left of the line, unless it is zero.

@<Local variables for line breaking@>=
@!disc_break:boolean; {was the current break at a discretionary node?}

@ @<Justify the line ending at breakpoint |p|, and append it...@>=
@<Modify the end of the line to reflect the nature of the break and to include
	\.{\\rightskip}; also set the proper value of |disc_break|@>;
@<Put the \(l)\.{\\leftskip} glue at the left@>;
@<Call the packaging subroutine, setting |just_box| to the justified box@>;
@<Append the new box to the current vertical list, followed by the list of
	special nodes taken out of the box by the packager@>;
@<Append a penalty node, if a nonzero penalty is appropriate@>

@ At the end of the following code, |q| will point to the final node on the
list about to be justified.

@<Modify the end of the line...@>=
q←cur_break(p); disc_break←false;
if q≠null then {|q| cannot be a |char_node|}
	if type(q)=glue_node then
		begin delete_glue_ref(glue_ptr(q));
		glue_ptr(q)←right_skip;
		subtype(q)←right_skip_code+1; add_glue_ref(right_skip);
		goto done2;
		end
	else	begin if type(q)=disc_node then
			@<Change discretionary to compulsory and set
				|disc_break←true|@>;
		if (type(q)=math_node)∨(type(q)=kern_node) then width(q)←0;
		end
else	begin q←temp_head;
	while link(q)≠null do q←link(q);
	end;
@<Put the \(r)\.{\\rightskip} glue after node |q|@>;
done2:

@ @<Change discretionary to compulsory...@>=
begin t←replace_count(q);
@<Destroy the |t| nodes following |q|, but save the last one if it is
	a kern; make |r| point to the next node@>;
if post_break(q)≠null then @<Transplant the post-break list@>;
if pre_break(q)≠null then @<Transplant the pre-break list@>;
link(q)←r; disc_break←true;
end

@ A subtle bug that would perhaps never have been detected is avoided here
by preserving a kern node that just might equal |cur_break(next_break(p))|.
The kern preserved here will be pruned away, in normal circumstances.

@<Destroy the |t| nodes following |q|...@>=
if t=0 then r←link(q)
else	begin while t>1 do
		begin s←link(s); decr(t);
		end;
	if is_char_node(s) then s←link(s)
	else if type(s)≠kern_node then s←link(s);
	r←link(s); link(s)←null;
	flush_node_list(link(q)); replace_count(q)←0;
	end

@ We move the post-break list from inside node |q| to the main list by
reattaching it just before the present node |r|, then resetting |r|.

@<Transplant the post-break list@>=
begin s←post_break(q);
while link(s)≠null do s←link(s);
link(s)←r; r←post_break(q); post_break(q)←null;
end

@ We move the pre-break list from inside node |q| to the main list by
reattaching it just after the present node |q|, then resetting |q|.

@<Transplant the pre-break list@>=
begin s←pre_break(q); link(q)←s;
while link(s)≠null do s←link(s);
pre_break(q)←null; q←s;
end

@ @<Put the \(r)\.{\\rightskip} glue after node |q|@>=
r←new_param_glue(right_skip_code); link(r)←link(q); link(q)←r; q←r

@ The following code begins with |q| at the end of the list to be
justified. It ends with |q| at the beginning of that list, and with
|link(temp_head)| pointing to the remainder of the paragraph, if any.

@<Put the \(l)\.{\\leftskip} glue at the left@>=
r←link(q); link(q)←null; q←link(temp_head); link(temp_head)←r;
if left_skip≠zero_glue then
	begin r←new_param_glue(left_skip_code);
	link(r)←q; q←r;
	end

@ Now |q| points to the hlist that represents the current line of the
paragraph. We need to compute the appropriate line width, pack the
line into a box of this size, and shift the box by the appropriate
amount of indentation.

@<Local variables for line...@>=
@!cur_width:scaled; {width of line number |cur_line|}
@!cur_indent:scaled; {left margin of line number |cur_line|}

@ @<Call the packaging subroutine...@>=
if cur_line>last_special_line then
	begin cur_width←second_width; cur_indent←second_indent;
	end
else if par_shape_ptr=null then
	begin cur_width←first_width; cur_indent←first_indent;
	end
else	begin cur_width←mem[par_shape_ptr+2*cur_line].sc;
	cur_indent←mem[par_shape_ptr+2*cur_line-1].sc;
	end;
just_box←hpack(q,cur_width,exactly);
shift_amount(just_box)←cur_indent

@ @<Append the new box to the current vertical list...@>=
append_to_vlist(just_box);
if adjustments≠null then
	begin link(tail)←adjustments;
	repeat tail←link(tail);
	until link(tail)=null;
	end

@ Penalties between the lines of a paragraph come from widow lines, from
the |inter_line_penalty| parameter, and from lines that end at
discretionary breaks.  Breaking between lines of a two-line paragraph gets
two contributions of widow-line penalties. The local variable |pen| will
be set to the sum of all relevant penalties for the current line.

@<Append a penalty node, if a nonzero penalty is appropriate@>=
pen←inter_line_penalty;
if (cur_line=already+1)∧(best_line≠already+2) then pen←pen+widow_penalty;
if cur_line+2=best_line then pen←pen+final_widow_penalty;
if disc_break then pen←pen+broken_penalty;
if pen≠0 then
	begin r←new_penalty(pen);
	link(tail)←r; tail←r;
	end